- Title
- Minimizing the regularity of maximal regular antichains of 2- and 3-sets
- Creator
- Kalinowski, Thomas; Leck, Uwe; Reiher, Christian; Roberts, Ian T.
- Relation
- Australasian Journal of Combinatorics Vol. 64, Issue 2, p. 277-288
- Relation
- http://ajc.maths.uq.edu.au/?page=get_volumes&volume=64
- Publisher
- Centre for Discrete Mathematics & Computing
- Resource Type
- journal article
- Date
- 2016
- Description
- Let n ≥ 3 be a natural number. We study the problem of finding the smallest r such that there is a family Α of 2-subsets and 3-subsets of [n] = {1, 2,...,n} with the following properties: (1) Α is an antichain, i.e., no member of Α is a subset of any other member of A, (2) A is maximal, i.e., for every X ∈ 2[n]\A there is an A ∈ A with X ⊆ A or A ⊆ X, and (3) A is r-regular, i.e., every point x ∈ [n] is contained in exactly r members of A. We prove lower bounds on r, and we describe constructions for regular maximal antichains with small regularity.
- Subject
- maximal regular antichains; lower bounds; 2- and 3-sets
- Identifier
- http://hdl.handle.net/1959.13/1320273
- Identifier
- uon:24113
- Identifier
- ISSN:1034-4942
- Language
- eng
- Full Text
- Reviewed
- Hits: 2276
- Visitors: 2734
- Downloads: 328
Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|
View Details Download | ATTACHMENT02 | Publisher version (open access) | 272 KB | Adobe Acrobat PDF | View Details Download |